#include <iostream>
#include <memory>
#include <algorithm>

using namespace std;

class SegTree {
public:
    class Data {
    public:
        int sum, inmax, lmax, rmax;
        Data(int s, int i, int l, int r)
        : sum(s), inmax(i), lmax(l), rmax(r) {}
        Data(): Data(0, 0, 0, 0) {}
        void operator=(const Data& d) {
            sum = d.sum; inmax = d.inmax;
            lmax = d.lmax; rmax = d.rmax;
        }
    };
    SegTree(int *a, int size)
    : arr(a), ans(), tmp(), tree(new Data[size << 2 + 5]) {
         build(1, 1, size);
    }
    ~SegTree() { delete [] tree; }
    void modify(int ind, int l, int r, int x, int y);
    void query(int ind, int l, int r, int x, int y);
    void print() { cout << ans.inmax << endl; }
private:
    SegTree() = delete;
    void build(int ind, int l, int r);
    void up(int ind, int ll, int rr);
    void up(Data&, Data&, Data&);
    int& sum(int ind) { return tree[ind].sum; }
    int& lmax(int ind) { return tree[ind].lmax; }
    int& rmax(int ind) { return tree[ind].rmax; }
    int& inmax(int ind) { return tree[ind].inmax; }
    int lc(int ind) { return ind << 1; }
    int rc(int ind) { return ind << 1 | 1; }
    int *arr;
    Data *tree, ans, tmp;
};

int main() {
    int n, m, *val, k, x, y;
    cin >> n >> m;
    val = new int[n];
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
    }
    SegTree t(val, n);
    for (int i = 0; i < m; ++i) {
        cin >> k >> x >> y;
        switch (k) {
            case 1: {
                if (x > y) swap(x, y);
                t.query(1, 1, n, x, y);
                t.print();
            } break;
            case 2: {
                t.modify(1, 1, n, x, y);
            } break;
        }
    }
    delete [] val;
    return 0;
}

void SegTree::build(int ind, int l, int r) {
    if (l == r) {
        sum(ind) = lmax(ind) = rmax(ind)
                 = inmax(ind) = arr[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(lc(ind), l, mid);
    build(rc(ind), mid + 1, r);
    up(ind, lc(ind), rc(ind));
    return ;
}

void SegTree::up(int ind, int ll, int rr) {
    up(tree[ind], tree[ll], tree[rr]);
}

void SegTree::up(Data& i, Data& l, Data& r) {
    i.sum = l.sum + r.sum;
    i.lmax = max(l.lmax, l.sum + r.lmax);
    i.rmax = max(r.rmax, r.sum + l.rmax);
    i.inmax = max(l.inmax, max(r.inmax, l.rmax + r.lmax));
}

void SegTree::modify(int ind, int l, int r, int x, int y) {
    if (l == r) {
        sum(ind) = inmax(ind) = lmax(ind) = rmax(ind) = y;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lc(ind), l, mid, x, y);
    else modify(rc(ind), mid + 1, r, x, y);
    up(ind, lc(ind), rc(ind));
    return ;
}

void SegTree::query(int ind, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        if (x == l) {
            ans = tree[ind];
        } else {
            up(tmp, ans, tree[ind]);
            swap(tmp, ans);
        }
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) query(lc(ind), l, mid, x, y);
    if (y > mid) query(rc(ind), mid + 1, r, x, y);
}